public class 一和零 {
    public static int zeros;
    public static int ones;
    public int findMaxForm(String[] strs, int m, int n) {
        return dfs(strs,m,n,0);
    }

    private int dfs(String[] strs, int m, int n, int pos) {
        if (pos == strs.length) {
            return 0;
        }
        int ans = Integer.MIN_VALUE;
        // 不选这个
        ans = dfs(strs,m,n,pos + 1);
        // 选这个
        zerosAndOnes(strs[pos]);
        if (m - zeros >= 0 && n - ones >= 0) {
            ans = Math.max(ans,dfs(strs,m - zeros,n - ones,pos + 1) + 1);
        }
        return ans;
    }

    private void zerosAndOnes(String str) {
        ones = 0;
        zeros = 0;
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == '1') {
                ones++;
            }
        }
        zeros = str.length() - ones;
    }

    public int findMaxForm1(String[] strs, int m, int n) {
        int[][][] dp = new int[m + 1][n + 1][strs.length];
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                for (int k = 0; k < strs.length; k++) {
                    dp[i][j][k] = -1;
                }
            }
        }
        return dfs1(strs,m,n,0,dp);
    }

    private int dfs1(String[] strs, int m, int n, int pos,int[][][] dp) {
        if (pos == strs.length) {
            return 0;
        }
        if (dp[m][n][pos] != -1) {
            return dp[m][n][pos];
        }
        int ans = Integer.MIN_VALUE;
        // 不选这个
        ans = dfs1(strs,m,n,pos + 1,dp);
        // 选这个
        zerosAndOnes(strs[pos]);
        if (m - zeros >= 0 && n - ones >= 0) {
            ans = Math.max(ans,dfs1(strs,m - zeros,n - ones,pos + 1,dp) + 1);
        }
        dp[m][n][pos] = ans;
        return ans;
    }


    public int findMaxForm2(String[] strs, int m, int n) {
        int[][][] dp = new int[strs.length + 1][m + 1][n + 1];
        for (int i = strs.length - 1; i >= 0; i--) {
            zerosAndOnes(strs[i]);
            for (int j = 0; j <= m; j++) {
                for (int k = 0; k <= n; k++) {
                    dp[i][j][k] = dp[i + 1][j][k];
                    if (j - zeros >= 0 && k - ones >= 0) {
                        dp[i][j][k] = Math.max(dp[i][j][k],dp[i + 1][j - zeros][k - ones] + 1);
                    }
                }
            }
        }
        return dp[0][m][n];
    }
}
